题目分析

这个题目小伙伴们会下意识的想到使用记忆化+DFS来解决，但是因为题目的特殊性，会导致记忆化DFS也会占用非常多的时间，所以还会给小伙伴们推荐动态规划的解法。

记忆化+DFS

在常规的记忆化DFS算法中，使用memory数组或者哈希表保存已搜索过的状态，下一次访问时，如果存在于哈希表中，直接取出即可，不需要进行搜索。

假设本题最多经历11次中转，如果已经搜索到了某个点k，可能经过了10次中转，花费了100元，但是这次经过了1次中转，花费了110元，那么可能10次中转的最后无法抵达终点，而1次中转的可以抵达终点，说明仍然需要重新搜索该节点。

但是仍然可以使用记忆化，如果存在某次遍历，中转次数小于本次，并且花费小于本次，那么就可以省去本次遍历，这也是非常好理解的。但是条件稍微苛刻一些，记忆化的效率一般。

算法的**时间复杂度为$O(k x n!)$，空间复杂度为$O(nk)$**，因为可以记忆化剪枝，所以时间复杂度远远小于这个值，本题可以勉强通过。

下面是Java语言的题解

class Solution {
    private int cost = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] map = new int[n][n];
        for (int[] flight : flights) {
            map[flight[0]][flight[1]] = flight[2];
        }
        int[][] visit = new int[n][k + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visit[i], Integer.MAX_VALUE);
        }
        dfs(n, src, dst, k, map, visit, 0);
        return cost == Integer.MAX_VALUE ? -1 : cost;
    }

    private void dfs(int n, int cur, int dst, int k, int[][] map, int[][] visit, int curCost) {
        if (cur == dst) {
            cost = Math.min(cost, curCost);
            return;
        }
        if (k < 0) {
            return;
        }
        for (int i = k; i < visit[0].length; i++) {
            if (visit[cur][k] <= curCost) {
                return;
            }
        }
        visit[cur][k] = curCost;
        for (int i = 0; i < n; i++) {
            if (map[cur][i] >= 1) {
                dfs(n, i, dst, k - 1, map, visit, curCost + map[cur][i]);
            }
        }
    }
}

DP

DP的思想就非常巧妙，dp[i][j]表示经过i次中转到达第j个城市需要的花费。

$$dp[i][j] = min(dp[i][j], dp[i - 1][k] + cost[k][j])$$
其中cost[k][j]表示从k到j节点的花费，最后返回dp[0][src], dp[1][src], …, dp[k][src]中的最小值即可。

算法的时间复杂度为$O(k x n^2)$，空间复杂度为$O(nk)$

下面是Java语言的题解

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int MAX = 1000000;
        int[][] dp = new int[k + 1][n];
        Arrays.fill(dp[0], MAX);
        for (int[] flight : flights) {
            if (flight[0] == src) {
                dp[0][flight[1]] = flight[2];
            }
        }
        int res = dp[0][dst];
        for (int i = 1; i < k + 1; i++) {
            Arrays.fill(dp[i], MAX);
            for (int[] flight : flights) {
                dp[i][flight[1]] = Math.min(dp[i][flight[1]], dp[i - 1][flight[0]] + flight[2]);
            }
            res = Math.min(res, dp[i][dst]);
        }
        return res == MAX ? -1 : res;
    }
}

刷题总结

DP的思想是保存之前计算过的结果，那么看起来记忆化DFS也是一种DP，小伙伴们要好好理解两者之间的关系。